use std::collections::HashMap;

// 1. max_value sliding window
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    if nums.len() < 1 {
        return vec![];
    }
    let mut queue: Vec<i32> = vec![0];
    let mut result: Vec<i32> = vec![];
    for i in 0..nums.len() {
        if nums[i] > queue[0] {
            queue.clear();
        }
        queue.push(nums[i]);
        if queue.len() > k as usize {
            queue.remove(0);
        }
        if i >= (k-1) as usize {
            result.push(queue[0]);
        }
    }
    result
}

// 2. no repeat char of the longest substring (double Pointer)
pub fn length_of_longest_substring(s: &str) -> i32 {
    let s = s.chars().collect::<Vec<char>>();
    let n = s.len();
    let mut set: Vec<char> = vec![];
    let mut res = 0;
    let mut i = 0;
    let mut j = 0;
    while i < n && j < n {
        if !set.contains(&s[j]) {
            set.push(s[j]);
            j += 1;
            res = i32::max(res, (j - i) as i32);
        } else {
            set.remove(0);
            i += 1;
        }
    }
    res
}
// 2.1 (hashmap)
pub fn length_of_longest_substring_hashmap(s: &str) -> usize {
    let s = s.chars().collect::<Vec<char>>();
    let mut map: HashMap<char, usize> = HashMap::new();
    let mut left = 0;
    let mut right = 0;
    let mut res = 0;
    for c in s {
        let temp = map.get_mut(&c);
        if let Some(v) = temp {
            left = usize::max(*v, left);
            *v = right + 1;
        } else {
            map.insert(c, right+1);
        }
        res = usize::max(res, right-left+1);
        right += 1;
    }
    res
}
// 2.2 (vec 256(char) instead of hashmap)
pub fn length_of_longest_substring_vec(s: &str) -> usize {
    let s = s.chars().map(|c| c as u8 as usize).collect::<Vec<usize>>();
    let mut char_index = vec![0_usize; 256];
    let mut left= 0_usize;
    let mut right = 0_usize;
    let mut res = 0_usize;
    for c in s {
        left = usize::max(char_index[c], left);
        res = usize::max(res, right-left+1);
        char_index[c] = right + 1;
        right += 1;
    }
    res
}

// 3. Find all letter ectopic words in the string
pub fn find_anagrams(s: &str, p: &str) -> Vec<usize> {
    let a = 'a' as u8;
    let s = s.chars().map(|c| (c as u8 - a) as usize).collect::<Vec<usize>>();
    let p = p.chars().map(|c| (c as u8 - a) as usize).collect::<Vec<usize>>();
    let mut s_arr = vec![0; 26];
    let mut p_arr = vec![0; 26];
    for i in 0..p.len() {
        s_arr[s[i]] += 1;
        p_arr[p[i]] += 1;
    }
    let mut res: Vec<usize> = vec![];
    let mut i = 0;
    let mut j = p.len();
    while j < s.len() {
        if s_arr == p_arr {
            res.push(i);
        }
        s_arr[s[i]] -= 1;
        i += 1;
        s_arr[s[j]] += 1;
        j += 1;
    }
    if s_arr == p_arr {
        res.push(i)
    }
    res
}
